t=int(input())
while t:
n=int(input())
l=list(map(int,input().split()))
if n==1:
print(l[0])
else:
ans=l[0]+l[-1]
for i in range(1,n):
ans+=abs(l[i]-l[i-1])
for i in range(1,n-1):
if l[i]>l[i-1] and l[i]>l[i+1]:
ans-=l[i]-max(l[i-1],l[i+1])
if l[0]>l[1]:
ans-=l[0]-l[1]
if l[-1]>l[-2]:
ans-=l[-1]-l[-2]
print(ans)
t-=1#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7;
const int INF_INT = 0x3f3f3f3f;
const long double PI = acosl(-1.), EPS = 1e-9;
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> v(n);
ll curug = 0;
for(int i=0;i<n;i++){
cin >> v[i];
if(i == 0) curug += v[i];
else curug += abs(v[i] - v[i-1]);
}
curug += v[n-1];
if(n == 1){
cout << curug/2 << "\n";
return;
}
if(n >=2 && v[0] > v[1]) {
curug -= v[0] - v[1];
v[0] = v[1];
}
for(int i=1;i<(n-1);i++){
if(v[i] > v[i-1] && v[i] > v[i+1]){
curug -= v[i] - max(v[i-1], v[i+1]);
v[i] = max(v[i-1], v[i+1]);
}
}
if(n >= 2) curug -= max(v[n-1] - v[n-2], 0);
cout << curug << "\n";
}
//cout << fixed << setprecision(6)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("in", "r", stdin); test input
int t;
cin >> t;
while(t--){
solve();
}
}
1667B - Optimal Partition | 1668B - Social Distance |
88B - Keyboard | 580B - Kefa and Company |
960A - Check the string | 1220A - Cards |
897A - Scarborough Fair | 1433B - Yet Another Bookshelf |
1283B - Candies Division | 1451B - Non-Substring Subsequence |
1408B - Arrays Sum | 1430A - Number of Apartments |
1475A - Odd Divisor | 1454B - Unique Bid Auction |
978C - Letters | 501B - Misha and Changing Handles |
1496A - Split it | 1666L - Labyrinth |
1294B - Collecting Packages | 1642B - Power Walking |
1424M - Ancient Language | 600C - Make Palindrome |
1669D - Colorful Stamp | 1669B - Triple |
1669A - Division | 1669H - Maximal AND |
1669E - 2-Letter Strings | 483A - Counterexample |
3C - Tic-tac-toe | 1669F - Eating Candies |